//
// Created by xili on 2024/9/20 18:03.
// GO BIG OR GO HOME.
//
#include "leetcode.h"

//暴力递归
class Solution1 {
public:
    int coinChange(vector<int> &coins, int amount) {
        int ans = f(coins, amount);
        return ans == INT16_MAX ? -1 : ans;
    }

    int f(vector<int> &coins, int v) {
        int ans = INT16_MAX;
        if (!v) {
            return 0;
        }
        if (v < 0) {
            return ans;
        }
        for (auto &it: coins) {
            ans = min(ans, f(coins, v - it) + 1);
        }
        return ans;
    }
};

//记忆化搜索
class Solution2 {
public:
    int coinChange(vector<int> &coins, int amount) {
        vector<int> dp(amount + 1, -1);
        int ans = f(coins, amount, dp);
        return ans == INT32_MAX ? -1 : ans;
    }

    int f(vector<int> &coins, int v, vector<int> &dp) {
        int ans = INT32_MAX;
        if (v < 0) {
            return ans;
        }
        if (dp[v] != -1) {
            return dp[v];
        }
        if (!v) {
            return 0;
        }
        for (auto &it: coins) {
            int res = f(coins, v - it, dp);
            if (res != INT32_MAX) {
                ans = min(ans, res + 1);
            }
        }
        dp[v] = ans;
        return ans;
    }
};

//严格位置依赖
class Solution3 {
public:
    int coinChange(vector<int> &coins, int amount) {
        vector<int> dp(amount + 1, INT32_MAX);
        dp[0] = 0;  // 凑成 0 元不需要硬币
        // 对于每一个金额，从 1 到 amount 进行计算
        for (int i = 1; i <= amount; ++i) {
            // 尝试每一种硬币
            for (int coin: coins) {
                if (i - coin >= 0 && dp[i - coin] != INT32_MAX) {
                    dp[i] = min(dp[i], dp[i - coin] + 1);
                }
            }
        }
        // 如果 dp[amount] 仍然是 INT_MAX，说明无法凑出该金额
        return dp[amount] == INT32_MAX ? -1 : dp[amount];
    }
};
